#ifndef DOUBLECHAIN_H_
#define DOUBLECHAIN_H_

#include <iostream>
#include <sstream>
#include <string>
#include <cstdlib>
#include "myExceptions.h"

using namespace std;

template <class T>
struct chainNode 
{
    // data members
    
    T _element;
    chainNode<T> *_next;
    chainNode<T> *_prev;
    chainNode(const T &element)
	:_element(element), _next(NULL), _prev(NULL)
        {}
};

template<class T>
class doubleChain {
	public:
	    //constructor, copy constructor, overload = 
		doubleChain():_head(NULL), _tail(NULL), _length(0) {}
		doubleChain(const doubleChain<T> &s);
		doubleChain(const T& element, chainNode<T>*p);
		doubleChain& operator= (const doubleChain<T> &s);
        ~doubleChain();
        
		void clear();
        void reverse();
        void print(ostream &os);
		
        void push_back(const T& element);
		void pop_back();
		void push_front(const T& element);
		void pop_front();
		
		void insert(chainNode<T>* pos, const T &element);
		void erase(chainNode<T>* pos);
		
		
		int length() { return _length; }
		void remove(const T &element);
		chainNode<T>* find(const T &element);
		
		class iterator;
		iterator begin() { return iterator(_head); }
		iterator end()   { return iterator(NULL); }
		
		// iterator for chain 
		class iterator
		{
			public:
			    typedef forward_iterator_tag iterator_category;
				typedef T value_type;
				typedef ptrdiff_t difference_type;
				typedef T* pointer;
				typedef T& reference;
				
				// constructor 
				iterator(chainNode<T>* node = NULL)
				        { _node = node; }
				T& operator*()  const { return _node->_element; }
				T* operator->() const { return &_node->_element; }
				
				// increment
				iterator& operator++()      // preincrement
				        { _node = _node->_next; }
				iterator operator++(int)
				        { iterator old = *this;
						  _node = _node->_next;
						  return old;}
				
				// increment
				iterator& operator--()      // preincrement
				        { _node = _node->_prev; }
				iterator operator--(int)
				        { iterator old = *this;
						  _node = _node->_prev;
						  return old;}
						  
				// equality testing
				bool operator!= (const iterator right) const
				        { return _node != right._node; }
				bool operator== (const iterator right) const
				        { return _node == right._node; }
			
			protected:
			    chainNode<T>* _node;
		};
	private:
	    void check_node(chainNode<T>* node);
	    chainNode<T>* _head;
		chainNode<T>* _tail;
		int _length;
};


template<class T>
doubleChain<T>::doubleChain(const doubleChain &s)
:_head(NULL), _tail(NULL)
{
	if (s._head == NULL)
		return;
	
	chainNode<T>* currentNode = s._head;
	T element;
	while(currentNode != NULL) {
		element = currentNode->_element;
		push_back(element);
		currentNode = currentNode->_next;
	}
	_length = s._length;
}

template<class T>
inline doubleChain<T>& doubleChain<T>::
operator= (const doubleChain &s)
{
	if (this != &s) {
		doubleChain<T> x(s);
		_head = x._head;
        _tail = x._tail;
        _length = x._length;		
	}
	
	return *this;
}


template<class T>
doubleChain<T>::
~doubleChain()
{
	clear();
}

template<class T>
inline void doubleChain<T>::
reverse()
{
	if (_head == NULL || _head == _tail) {
		return;
	}
	int ret = length();
	chainNode<T>* it = _head;
    chainNode<T>* it_end = _tail;
    
	ret /= 2;
    while(ret--) {
		if (it_end->_next == it)
			break;
						
		swap(it->_element, it_end->_element);
		it = it->_next;
		it_end = it_end->_prev;
	}	
}

template<class T>
inline void doubleChain<T>::
print(ostream &os)
{
	if (_head == NULL) {
		return;
	}
	else {
		chainNode<T> *p = _head;
		while(p != NULL) {
			os << p->_element << " ";
			p = p->_next;
		}
	}
	os << endl;
}

template<class T>
inline void doubleChain<T>::
push_back(const T &element)
{
	if (_head == NULL) {
		_head = new chainNode<T>(element);
		_tail = _head;
	}
	else {
		chainNode<T>* temp = new chainNode<T>(element);
		_tail->_next = temp;
		temp->_prev = _tail;
		_tail = temp;
	}
	_length ++;
}

template<class T>
inline void doubleChain<T>::
clear()
{
	chainNode<T>* it = _head;

	while (it != _tail) {
		_head = _head->_next;
		delete it;
		it = _head;
	}
	
	delete it;
	_head = NULL;
	_tail = NULL;
	_length = 0;
}

template<class T>
inline void doubleChain<T>::
pop_back()
{
	if (_head == NULL)
		return;
	else if (_head == _tail) {
		delete _head;
		_head = NULL;
		_tail = NULL;
	}
	else {
		chainNode<T>* p = _tail->_prev;
		
		delete _tail;
		_tail = p;
		_tail->_next = NULL;

	}
	_length --;
}

template<class T>
inline void doubleChain<T>::
push_front(const T &element)
{
	if (_head == NULL) {
		push_back(element);
	}
	else{
		chainNode<T>* temp = _head;
		_head = new chainNode<T>(element);
		_head->_next = temp;
		temp->_prev = _head;
	}
	_length++;
}

template<class T>
inline void doubleChain<T>::
pop_front()
{
	if (_head == NULL)
		return;
	chainNode<T>* temp = _head;
	
	_head = _head->_next;
	_head->_prev = NULL;
	delete temp;
	_length --;
}

template<class T>
inline void doubleChain<T>::
insert(chainNode<T>* pos, const T &element)
{
//	check_node(pos);
	
	if (pos == _tail || _head == NULL) {
		push_back(element);
	}
	else {
		chainNode<T>* temp = new chainNode<T>(element);
		temp->_next = pos->_next;
		temp->_prev = pos;
		pos->_next = temp;
        temp->_next->_prev = temp;	
	}
	_length++;
}

template<class T>
inline void doubleChain<T>::
erase(chainNode<T>* pos)
{
//	check_node(pos);
	if (_head == NULL)
		return;
	
	if (pos == _tail) {
		pop_back();
	}
	else if (pos == _head)
		pop_front();
	else {
		pos->_prev->_next = pos->_next;
		pos->_next->_prev = pos->_prev;
		delete pos;
	}
	_length --;
}

template<class T>
inline chainNode<T>* doubleChain<T>::
find(const T& element)
{
	if (_head == NULL)
		return NULL;
	else {
		chainNode<T>* temp = _head;
		while(temp != NULL) {
			if (temp->_element == element)
				return temp;
			else
				temp = temp->_next;
		}
		return NULL;	
	}
}

template<class T>
inline void doubleChain<T>::
remove(const T& element)
{
	chainNode<T>* deleteNode =  find(element);
	erase(deleteNode);
}

template<class T>
inline ostream&
operator<< (ostream& os, const doubleChain<T>& list)
{
	list.print(os);
	return os;
}


#endif